The present invention relates generally to computer networks and, more specifically, to a technique for distributing processing loads among intermediate stations of a computer internetwork.
Communication in a computer internetwork involves the exchange of data between two or more entities interconnected by communication media. The entities are typically software programs executing on hardware computer platforms, such as end stations and intermediate stations. In particular, communication software executing on the stations correlate and manage data communication with other stations. The stations typically communicate by exchanging discrete packets or frames of data according to predefined protocols. A protocol, in this context, consists of a set of rules defining how the stations interact with each other.
Examples of intermediate stations include a router, a switch and a bridge, each of which generally comprises a processor. such as a central processing unit (CPU), and port interfaces for interconnecting a wide range of communication links and subnetworks. Broadly stated, the router implements network services such as route processing, path determination and path switching functions. The route processing function determines optimal routing for a packet based, e.g., on a destination address stored in a packet header, such as an Internet protocol (IP) header, whereas the path switching function allows a router to accept a packet on one interface and forward it on a second interface. The path determination, or forwarding decision, function selects the most appropriate interface for forwarding a packet. The switch, on the other hand, provides the basic functions of a bridge including filtering of data traffic by medium access control (MAC) address and xe2x80x9clearingxe2x80x9d of a MAC address based upon a source MAC address of a frame; in addition, the switch may implement forwarding decision and path switching operations of a router.
Often it may be desirable for the intermediate station, hereinafter referred to as a switch, to perform additional processing-intensive operations on a stream of data traffic. An example of such processing may involve policing of bandwidth utilization policies, such as usage parameter control or network parameter control policies. Violations of these policies typically occur when a transmitting station (xe2x80x9csenderxe2x80x9d) attempts to utilize more bandwidth than it is entitled to under the terms of the policies. Hence, it may be desired to have the switch record, e.g., all frame traffic of a particular type and within a particular time span that are transmitted from a particular sender to ensure that the sender does not exceed a particular threshold (e.g., 5 frames a second). Enforcement of the policies results in the switch discarding (filtering) those frames in violation of the bandwidth constraints. However, the accounting, auditing and/or record keeping operations needed to ensure that the bandwidth constraints are observed may tax the CPU resources of the switch.
Another example of desired processing-intensive operations for a switch involves checking for invalid digital signatures on packets received at the switch. Digital signatures are generally used in accordance with a well-known cryptographic technique for performing remote authentication known as public key cryptography. In this method of secure communication, each entity has a public encryption key and a private encryption key, and two entities can communicate knowing only each other""s public keys and, of course, their own private keys. To prove to a recipient of information that the sender is who it purports to be, the sender digitally encodes (xe2x80x9csignsxe2x80x9d) the information with its private key. If the recipient can decode (xe2x80x9cverifyxe2x80x9d) the information, it knows that the sender has correctly identified itself.
It may be desirable for the switch to check digital signatures on packets to verify that the packets orginate from a sender that is authorized to use the bandwidth of the network. Here, the authorized senders have access to a group private key and the switch has access to, or aquires, the complementary group public key. The authorized senders thus sign their packets with the group private key and the switch verifies those signatures upon receiving the packets. Those packets having unauthorized signatures may be filtered by the switch.
However, it typically takes longer for a switch to verify a signature than it takes to receive a small packet at wire speed, so an unauthorized sender could mount a xe2x80x9cdenial-of-servicexe2x80x9d attack by transmitting a stream of invalidly signed packets. Such an attack becomes particularly burdensome when the switch attempts to verify digital signatures on multicast packets. Checking of each packet at the switch consumes valuable CPU resources which typically cannot be spared because of their occupation with conventional switching operations. Each switch is generally independently responsible for verifying packets of a traffic stream and, as such, a single switch may be unable to keep up with the traffic of such an attack. Therefore, the present invention is directed to alleviating the processing-intensive burden placed on a switch of a computer internetwork.
The invention relates to a load distribution system for efficiently distributing processing-intensive loads among a plurality of intermediate stations in a computer inter-network. The intermediate stations include routers, bridges and/or switches configured with monitoring and filtering agents that communicate via a defined protocol to implement the system. According to the invention, those stations configured with agents and having available resources cooperate to execute the loads which generally comprise verification operations on digital signatures appended to frame and/or packet traffic traversing paths of the computer internetwork. The novel system includes various techniques that are directed to efficiently detecting and filtering unauthorized traffic, hereinafter referred to as packets, over portions of the internetwork protected as trust domains as well as unprotected portions of the internetwork, such as the Internet.
In a first technique of the inventive system, multiple switches share the verification load by independently processing a random selection of packets. Most senders of packets generally do not transmit unauthorized packets over the internetwork; therefore, rather than process (check) each packet, the first technique employs a plurality of switches to xe2x80x9cspot-checkxe2x80x9d a fraction of the packets. Notably, there is no need to coordinate processing among the switches. A second technique, however, contemplates examination of each packet, but in a manner that avoids redundancy. A hash function is invoked to assign packet checking responsibility to each switch configured with the monitoring and filtering agent. Communication among the agents resident on switches of a path traversed by the packets enables distinguishing of responsibility based on, e.g., even/odd destination addresses of the packets.
If apportioning of the processing load according to the second technique results in unbalanced division of work among the switches, a sophisticated hash function is employed that divides the packets into substantially more xe2x80x9cbucketsxe2x80x9d than the previous hash function. According to this third inventive technique, each switch is assigned an equal number of buckets and if any switch is burdened with excessive processing responsibility, additional buckets are exchanged among the switches.
In a trust domain, an enterprise trusts only those switches within its domain, yet packets are often exchanged with an xe2x80x9coutsidexe2x80x9d network, such as the Internet. A fourth technique of the inventive load distribution system specifies the use of a flag in the header of the packet to indicate whether the packet has been verified by a trusted switch. The flag may be contained with an unused field of the header or, alternatively, it may be part of a mini-header added to the packet for use within the trust domain.
A fifth technique is directed to changing the fraction of packets that are xe2x80x9cspot-checkedxe2x80x9d on a per flow basis. A flow is a function of information stored in a packet header such as, in the case of an Internet protocol (IP) packet, source and destination IP address, source and destination transmission control protocol (TCP) ports and flow label. This aspect of the invention may be advantageously employed with the first technique such that once an unauthorized packet is identified via random spot-checking, a more careful examination of the source stream is conducted. Various approaches to changing the fraction of packets that are spot-checked for each flow are described further herein.
A sixth technique of the inventive system is directed to distributed filtering of packets using non-optimal routing. Since there may be only certain switches in the internetwork configured with the agents, this technique specifies changing an optimal path taken by a packet so it traverses switches having packet-verification capability.
Advantageously, the invention described herein distributes data traffic processing loads among intermediate stations of a computer internetwork in an efficient manner. More specifically, the invention provides a distributed filtering mechanism configured to avoid xe2x80x9cdenial-of-servicexe2x80x9d attacks on a switch of a computer internetwork.